package 二分查找;
import java.util.*;
/**
 * 该类用于在有序数组中查找目标值的范围。
 * 时间复杂度：O(log n)，空间复杂度：O(1)
 */
public class searchRange {
    /**
     * 使用两次二分查找查找目标值的范围。
     * 该方法通过分别查找目标值的左边界和右边界来确定范围。
     * @param nums 有序数组
     * @param target 目标值
     * @return 目标值在数组中的范围，如果不存在则返回 [-1, -1]
     */
    public int[] twoSearch(int[] nums, int target) {
        int leftBound = searchFlag(nums, target, true); // 查找左边界
        int rightBound = searchFlag(nums, target, false); // 查找右边界
        return new int[]{leftBound, rightBound}; // 返回范围
    }

    /**
     * 二分查找目标值的边界。
     * 该方法根据标志位查找目标值的左边界或右边界。
     * @param nums 有序数组
     * @param target 目标值
     * @param flag 标志位，true 表示查找左边界，false 表示查找右边界
     * @return 目标值在数组中的边界索引，如果不存在则返回 -1
     */
    private int searchFlag(int[] nums, int target, boolean flag) {
        int left = 0; // 左边界
        int right = nums.length - 1; // 右边界
        int idx = -1; // 初始化索引为 -1
        while(left <= right) { // 当左边界小于等于右边界时继续循环
            int mid = (left + right) >> 1; // 计算中间索引
            if(nums[mid] == target) { // 如果找到目标值
                idx = mid; // 更新索引
                if(flag == true) right = mid - 1; // 如果查找左边界，更新右边界
                else left = mid + 1; // 如果查找右边界，更新左边界
            } else if(target < nums[mid]) right = mid - 1; // 如果目标值小于中间元素，更新右边界
            else left = mid + 1; // 如果目标值大于中间元素，更新左边界
        }
        return idx; // 返回边界索引
    }

    /**
     * 使用双指针查找目标值的范围。
     * 该方法通过遍历数组查找目标值的起始和结束位置。
     * @param nums 有序数组
     * @param target 目标值
     * @return 目标值在数组中的范围，如果不存在则返回 [-1, -1]
     */
    public int[] twoPoint(int[] nums, int target) {
        int start = 0, end = 0; // 初始化起始和结束位置
        while(start < nums.length && nums[start] != target) // 查找起始位置
            start++;
        if(start == nums.length) // 如果未找到目标值
            return new int[]{-1, -1}; // 返回 [-1, -1]
        for(end = start; end < nums.length && nums[end] == target; end++); // 查找结束位置
        end = end - 1; // 调整结束位置
        return new int[]{start, end}; // 返回范围
    }

    /**
     * 使用二分查找和双指针查找目标值的范围。
     * 该方法通过二分查找找到目标值的位置，然后使用双指针查找范围。
     * @param nums 有序数组
     * @param target 目标值
     * @return 目标值在数组中的范围，如果不存在则返回 [-1, -1]
     */
    public int[] searchAndPoint(int[] nums, int target) {
        int left = 0; // 左边界
        int right = nums.length - 1; // 右边界
        int start = -1; // 初始化起始位置
        int end = -1; // 初始化结束位置
        while(left <= right) { // 当左边界小于等于右边界时继续循环
            int mid = (left + right) >> 1; // 计算中间索引
            if(nums[mid] == target) { // 如果找到目标值
                for(start = mid; start >= 0 && nums[start] == target; start--); // 查找起始位置
                for(end = mid; end < nums.length && nums[end] == target; end++); // 查找结束位置
                start++; // 调整起始位置
                end--; // 调整结束位置
                break; // 跳出循环
            } else if(target < nums[mid]) right = mid - 1; // 如果目标值小于中间元素，更新右边界
            else left = mid + 1; // 如果目标值大于中间元素，更新左边界
        }
        return new int[]{start, end}; // 返回范围
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取数组和目标值，并输出目标值在数组中的范围。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        String[] s = sc.nextLine().split(","); // 读取数组
        int target = sc.nextInt(); // 读取目标值
        int[] nums = new int[s.length]; // 创建数组
        for(int i = 0; i < s.length; i++) {
            nums[i] = Integer.parseInt(s[i]); // 解析数组
        }
        searchRange sr = new searchRange(); // 创建对象
        System.out.println("two search:" + Arrays.toString(sr.twoSearch(nums, target))); // 输出两次二分查找的结果
        System.out.println("two point:" + Arrays.toString(sr.twoPoint(nums, target))); // 输出双指针查找的结果
        System.out.println("search ptr:" + Arrays.toString(sr.searchAndPoint(nums, target))); // 输出二分查找和双指针查找的结果
        sc.close(); // 关闭扫描器
    }
}
